package org.example;

import lombok.AllArgsConstructor;
import lombok.Data;

/**
 * 链表回文
 * @Auther: wangbw
 * @Date:2020/11/10
 * @Description: org.example
 * @version: 1.0
 */
public class Palindrome {
    @Data
    @AllArgsConstructor
    static class Node {
        private String data;
        private Node next;
    }

    public static void main(String[] args) {
        Node head = createLinked();
        print(head);
        Boolean flag = isPalindrome(head);
        System.out.println(flag);
    }

    /**
     * 快慢指针定位中点；
     * 慢指针改变后半部分的指针指向
     * 然后2个指针一个从头开始，一个从尾巴开始逐个比较。
     * 注意链表长度分为奇偶情况， 奇数情况慢指针会停留在中间的一个点； 偶数情况慢指针会停留在中间2个点靠后位置的点。
     * @param head
     * @return
     */
    private static Boolean isPalindrome(Node head) {
        if (head == null || head.next == null)
            return true;
        Node slow = head;
        Node fast = head;
        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        if (fast != null)
            slow = slow.next;
        Node pre = reversal(slow);

        while (pre != null){
            if(head.getData() != null && head.getData().equals(pre.getData())){
                head = head.next;
                pre = pre.next;
            }else{
                return false;
            }
        }
        return true;
    }

    private static Node reversal(Node slow) {
        Node pre = null;
        Node cur = slow;
        while (cur != null){
            Node next = cur.next;
            cur.setNext(pre);
            pre = cur;
            cur = next;
        }
        return pre;
    }

    private static Node createLinked() {
        Node start0 = new Node("0", null);
        Node start1 = new Node("1", null);
        Node start2 = new Node("2", null);
        Node start11 = new Node("12", null);
        Node start00 = new Node("0", null);
        start0.setNext(start1);
        start1.setNext(start2);
        start2.setNext(start11);
        start11.setNext(start00);
        return start0;
    }

    static void print(Node headArg){
        Node head = headArg;
        while (head !=null){
            System.out.print(head.data + "  ->");
            head = head.next;
        }
        System.out.println("  null");
    }
}
